package org.liaohailong.helloworld;

import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
import java.util.TreeSet;

/**
 * Author: liaohailong
 * Time: 2021/4/25 09:15
 * Describe:
 */
public class SortMethod {
    public static void main(String[] args) {
        final int count = 1000000;
        final int start = -count / 2;
        final int end = count / 2;
        final int[] origin = new int[count];
        int pos = 0;
        for (int i = start; i < end; i++) {
            origin[pos] = i;
            pos++;
        }

        // 乱序 - 数组
//        ArrayList<Integer> src = new ArrayList<>();
//        for (int i : origin) src.add(i);
//        AUtil.printCostInMs(() -> Collections.shuffle(src), "shuffle array");
//        AUtil.print100(src);

        // 乱序 - 链表
//        LinkedList<Integer> src1 = new LinkedList<>();
//        for (int i : origin) src1.add(i);
//        AUtil.printCostInMs(() -> Collections.shuffle(src1), "shuffle linked");
//        AUtil.print100(src1);

        // 自定义乱序 - 数组
        final int[] copy = new int[origin.length];
        System.arraycopy(origin, 0, copy, 0, origin.length);
        AUtil.printCostInMs(() -> shuffle(copy), "custom shuffle");
        AUtil.print100(copy);

        // 移除所有负数
//        LinkedList<Integer> result = new LinkedList<>();
//        AUtil.printCostInMs(() -> removeNegative(copy, result), "removeNegative");
//        AUtil.print100(result);

        boolean useSimple = false;
        if (useSimple) {
            // 冒泡排序
            AUtil.printCostInMs(() -> simpleSort(copy), "simpleSort");
        } else {
            // 快速排序
            AUtil.printCostInMs(() -> quickSort(copy, 0, copy.length - 1), "quickSort");
        }
        AUtil.print100(copy);
    }

    /**
     * 移除所有负数
     *
     * @param arr    源数据
     * @param result 接收结果
     */
    private static void removeNegative(int[] arr, LinkedList<Integer> result) {
        result.clear();
        for (int i : arr) result.add(i);

        Iterator<Integer> iterator = result.iterator();
        while (iterator.hasNext()) {
            Integer next = iterator.next();
            if (next < 0) iterator.remove();
        }
    }

    public static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(int[] arr, int start, int end) {
        if (start < end) {
            int mid = partition(arr, start, end);
            quickSort(arr, start, mid);
            quickSort(arr, mid + 1, end);
        }
    }

    private static int partition(int[] arr, int start, int end) {
        int temp = arr[start];
        int i = start;
        int j = end;
        while (i < j) {
            while (arr[j] >= temp && i < j) j--;
            if (i < j) {
                arr[i] = arr[j];
                i++;
            }
            while (arr[i] <= temp && i < j) i++;
            if (i < j) {
                arr[j] = arr[i];
                j--;
            }
        }
        arr[i] = temp;
        return i;
    }

    /**
     * 冒泡排序
     *
     * @param arr 源数据
     */
    private static void simpleSort(int[] arr) {
        int j = arr.length;
        while (j > 0) {
            for (int i = 0; i < j - 1; i++) {
                int temp = arr[i];
                int nextIndex = i + 1;
                int next = arr[nextIndex];
                if (next < temp) {
                    arr[i] = next;
                    arr[nextIndex] = temp;
                }
            }
            j--;
        }
    }

    public static void shellSort(int[] arr) {
        int h = 1;
        while (h <= arr.length / 3) {
            h = 3 * h + 1;
        }

        for (int gap = h; gap > 0; gap = (gap - 1) / 3) {
            for (int i = gap; i < arr.length; i++) {
                for (int j = i; j > gap - 1; j -= gap) {
                    if (arr[j] < arr[j - gap]) swap(arr, j, j - gap);
                }
            }
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static final Map<Integer, Integer> orderMap = new HashMap<>();
    private static final int orderCount;

    static {
        orderMap.put(0, -1);
        orderMap.put(1, 1);
        orderMap.put(2, 1);
        orderMap.put(3, -1);
        orderMap.put(4, 1);
        orderMap.put(5, 1);
        orderMap.put(6, -1);
        orderMap.put(7, 1);
        orderMap.put(8, 1);
        orderMap.put(9, -1);
        orderCount = orderMap.size();
    }

    /**
     * 乱序数组
     *
     * @param arr 源数据
     */
    private static void shuffle(int[] arr) {
        TreeSet<Integer> treeMap = new TreeSet<>((o1, o2) -> {
            int res = o1 & o2;
            int key = res % orderCount;
            if (key < 0) key = -key;
            return orderMap.get(key);
        });

        for (int i : arr) treeMap.add(i);
        int pos = 0;
        for (Integer integer : treeMap) {
            arr[pos] = integer;
            pos++;
        }
    }
}
